package algorithm.tree;

import algorithm.model.TreeNode;

/**
 * LeetCode
 * https://leetcode-cn.com/problems/balanced-binary-tree/submissions/
 * Easy
 *
 * Created by yzy on 2021-03-31 15:14
 */
public class BalancedBinaryTree {


    /**
     * 1ms, 99.97%
     * 38.4MB, 82.19%
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return balanceDepth(root, 1) > 0;
    }

    /**
     * 思路：
     * 1、一次递归。在判断子树平衡的同时返回高度。如果不平衡则返回-1
     * 2、快速失败。当判断到某一个子树不平衡时直接返回失败，不再往下递归。
     * @param node
     * @param depth
     * @return
     */
    private int balanceDepth(TreeNode node, int depth){
        if(node == null){
            return depth;
        }
        int leftDepth = balanceDepth(node.left, depth);
        if(leftDepth < 0) {
            return -1;
        }
        int rightDepth = balanceDepth(node.right, depth);
        if(rightDepth < 0){
            return -1;
        }
        if(Math.abs(leftDepth-rightDepth) <=1){
            return depth + Math.max(leftDepth, rightDepth);
        }
        return -1;
    }

}
